"""
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6
使用84题的解法：使用dp存储当前行和上面能构成的最大矩形
[
  ["1","0","1","0","0"],  使用最大矩形面积求 为 1
  ["2","0","2","1","1"],                       3
  ["3","1","3","2","2"],                       6
  ["4","0","0","3","0"]                        4
]
则最大为 6
"""


class Solution:
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        maxl = 0
        dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == 0:
                    dp[i][j] = int(matrix[i][j])
                elif matrix[i][j] != "0":
                    dp[i][j] = dp[i - 1][j] + int(matrix[i][j])
            maxl = max(self.largestRectangleArea(dp[i]), maxl)
        return maxl

    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        maxArea = 0
        stack = []
        for i in range(len(heights)):
            if not stack:
                stack.append(heights[i])
            elif stack[-1] <= heights[i]:
                stack.append(heights[i])
            else:
                j = i - 1
                while heights[i] < stack[j] and j >= 0:
                    maxArea = max(maxArea, stack[j] * (i - j))
                    stack[j] = heights[i]
                    j -= 1
                stack.append(heights[i])
        for i, x in enumerate(stack):
            maxArea = max(maxArea, x * (len(heights) - i))
        return maxArea